package com.person.leetcode.editor.cn;

/**
 * 10.正则表达式匹配
 * 2022-05-05 17:36:12
 **/
public class Sequence_0010_RegularExpressionMatching {
    public static void main(String[] args) {
        Solution solution = new Sequence_0010_RegularExpressionMatching().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
//    class Solution {
//        public boolean isMatch(String s, String p) {
//            boolean res = true;
//            int i = 0, j = 0;
//            for (; i < s.length() && j < p.length(); ) {
//                char c = s.charAt(i);
//                char pc = p.charAt(j);
//                System.out.println(c);
//                System.out.println(pc);
//                //首个字符相比较
//                if (i == 0 && j == 0) {
//                    if ('.' == pc || c == pc) {
//                        i++;
//                        j++;
//                    } else {
////                        return false;
//                        j++;
//                    }
//                } else {
//                    //非首个字符
//                    if ('.' == pc || pc == c) {
//                        i++;
//                        j++;
//                    } else if ('*' == pc) {
//
//                        if (p.charAt(j - 1) == c || '.' == p.charAt(j - 1)) {
//                            i++;
//                        } else {
//                            j++;
//                        }
//
//                    } else {
//                        return false;
//                    }
//                }
//            }
//
//            if (i == s.length()){
//                if (j == p.length()){
//                    return true;
//                }else if (j == p.length() - 1 && p.charAt(p.length()-1) == '*'){
//                    return true;
//                }else{
//                    return false;
//                }
//            }else {
//                return false;
//            }
//        }
//
//        /**
//         * 简化正则字符串
//         * @param p
//         * @return
//         */
//        private String simplify(String p){
//            return "";
//        }
//    }

    class Solution {
        public boolean isMatch(String s, String p) {
            int sLen = s.length();
            int pLen = p.length();

            boolean[][] f = new boolean[sLen + 1][pLen + 1];
            f[0][0] = true;
            for (int sIndex = 0; sIndex <= sLen; ++sIndex) {
                for (int pIndex = 1; pIndex <= pLen; ++pIndex) {
                    if (p.charAt(pIndex - 1) == '*') {
                        //p匹配零次
                        f[sIndex][pIndex] = f[sIndex][pIndex - 2];
                        if (matches(s, p, sIndex, pIndex - 1)) {
                            f[sIndex][pIndex] = f[sIndex][pIndex] || f[sIndex - 1][pIndex];
                        }
                    } else {
                        if (matches(s, p, sIndex, pIndex)) {
                            f[sIndex][pIndex] = f[sIndex - 1][pIndex - 1];
                        }
                    }
                }
            }
            return f[sLen][pLen];
        }

        public boolean matches(String s, String p, int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p.charAt(j - 1) == '.') {
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
